package com.github.hgkmail.hello.leetcode101.dualpointer;

public class LC287FindTheDuplicateNumber {
    public int findDuplicate(int[] nums) {
        //base case
        if (nums.length<=1) {
            return 0;
        }
        //构造图，边为i->nums[i]（真的可以），再用快慢指针法
        int fast=0;
        int slow=0;
        do {
            if (fast<0 || fast>=nums.length) {
                return 0;
            }
            fast=nums[nums[fast]];
            slow=nums[slow];
        } while (fast!=slow);
        fast=0;
        while (fast!=slow) {
            fast=nums[fast];
            slow=nums[slow];
        }

        return fast;
    }

    public static void main(String[] args) {
        System.out.println(new LC287FindTheDuplicateNumber().findDuplicate(new int[]{1,3,4,2,2}));
    }
}
